package com.xzz.multipleMerge;

import java.math.BigDecimal;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author: hhz
 * @create: 2022-01-14 15:45
 * 786. 第 K 个最小的素数分数
 * 输入：arr = [1,2,3,5], k = 3
 * 输出：[2,5]
 * 解释：已构造好的分数,排序后如下所示:
 * 1/5, 1/3, 2/5, 1/2, 3/5, 2/3
 * 很明显第三个最小的分数是 2/5
 **/
public class KthSmallestPrimeFraction {
    public static void main(String[] args) {
        System.out.println(kthSmallestPrimeFraction(new int[]{1, 2, 3, 5}, 3));
        System.out.println(kthSmallestPrimeFraction(new int[]{1,7}, 1));
    }

    public static int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int[] res = new int[2];
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            double num1 =  arr[o1[0]]*1.0 /arr[o1[1]];
            double num2 =  arr[o2[0]]*1.0 /arr[o2[1]];
            return Double.compare(num1,num2);
        });
        int len = arr.length;
        for (int i = 0; i < len - 1; i++) {
            queue.offer(new int[]{i,len - 1});
        }

        while (k > 0 && !queue.isEmpty()) {
            int[] poll = queue.poll();
            k--;
            int i = poll[0];
            int j =  poll[1];
            res[0] = arr[i];
            res[1] = arr[j];
            if(j-1>i){
                queue.offer(new int[]{i, j-1});
            }
        }
        return res;

    }
}
